package crazy;

import java.util.Arrays;

//基数排序就是多轮桶式排序，程序从最低位到最高位一次排序
public class MultiKeyRadixSort
{
	public static void radixSort(int[] data, int radix, int d)
	{
		
		int arrayLength = data.length;
		int[] tmp = new int[arrayLength];
		int[] buckets = new int[radix];
		
		for (int i = 0, rate = 1; i < d; i++)
		{
			Arrays.fill(buckets, 0);//每次排序都要初始化buckets數組
			System.arraycopy(data, 0, tmp, 0, arrayLength);//在上一次排序的基础上 再次排序
			
			for (int j = 0; j < arrayLength; j++)
			{
				int subKey = tmp[j]/rate % radix;//得到相应位的0~9数字
				buckets[subKey]++;
			}
			System.out.println(java.util.Arrays.toString(buckets));
			/*
			[1, 1, 2, 1, 0, 0, 0, 0, 0, 0]
			[1, 2, 1, 0, 0, 0, 0, 0, 0, 1]
			[2, 2, 1, 0, 0, 0, 0, 0, 0, 0]
			[4, 1, 0, 0, 0, 0, 0, 0, 0, 0]
			 */
			
			for (int j = 1; j < radix; j++)
			{
				buckets[j] = buckets[j]+ buckets[j-1];
			}
			
			for (int m = arrayLength-1; m >= 0; m--)
			{
				int subKey = (tmp[m]/rate) % radix;
				data[--buckets[subKey]] = tmp[m];
			}
			
			//System.out.println(java.util.Arrays.toString(data));
			rate *= radix;
		}
	}
	
	public static void main(String[] args)
	{
		int[] data = {1100, 192, 221, 12, 13};
		//System.out.println(java.util.Arrays.toString(data)+"--b");
		radixSort(data, 10, 4);
		//System.out.println(java.util.Arrays.toString(data)+"--a");
	}
}
